The Uniformity Conjecture

Daniel Richardson

Mathematics, Bath University, Bath BA2 7AY, UK email: dsr@maths.bath.ac.uk

Abstract. This paper discusses the relationship between the syntactic length of expressions built up from the integers using field operations, radicals and exponentials and logarithms, and the smallness of non zero complex numbers defined by such expressions. The Uniformity Conjecture claims that if the expressions are written in an expanded form in which all the arguments of the exponential function have absolute value bounded by 1, then a small multiple of the syntactic length gives a bound for the number of decimal places needed to distinguish the defined number from zero. The consequences of this conjecture are compared with some known results about closeness of approximation from Liouville, Baker, Waldschmidt, Thue-Siegel-Roth. A few of many practical computational consequences are stated. Also the problem of searching for a possible counterexample to the Uniformity Conjecture is discussed and some preliminary results are given.

1 Introduction

The nested radical and exponential-logarithmic expressions are, roughly speaking, those which can be constructed from expressions for the integers using the operators \{+, −, ∗, /, \sqrt[n]{,} exp, log\}.

In the section below, the family of nested radical exponential-logarithmic expressions is described and the field of closed form numbers is defined. An expanded form is defined for the expressions, and the Uniformity Conjecture is stated. This claims that for expressions in expanded form, a small multiple of the syntactic length bounds the number of decimal places needed to distinguish the defined number from zero, if it is non zero.

In the following section, some consequences of the Uniformity Conjecture are compared with known, fairly simple, approximation estimates.

In the next section, a few of the many practical computational consequences of the Uniformity Conjecture are stated.

In the final section, the problem of searching for a counterexample to the Uniformity Conjecture is discussed, and some preliminary results are given.

2 Closed Form Numbers and the Uniformity Conjecture

2.1 Expressions

We assume, to begin with, some canonical representation for the integers. Then the set of nested radical exponential and logarithmic expressions is the smallest set of expressions so that:

1. All the representations of the integers are in the set.

2. If A and B are in the set so are A + B, A − B, A ∗ B, and A/B.

3. If A is in the set, so are (A), −A, exp(A) and log(A)

4. If A is in the set and n is a canonical representation of a natural number bigger than 1, then A^{1/n} is in the set.

Each nested radical exponential and logarithmic expression E is either undefined, or is interpreted as a real or complex number V (E), as follows.

1. If E is a representation of an integer, V (E) is that integer.

2. The operators are given the usual precedence in the absence of brackets.

3. If A and B are defined, then V (A + B), V (A − B), V (A ∗ B) and V (−A) are defined with the usual interpretation of the operators. If A is defined, and B is defined and V (B) is not zero, then V (A/B) is defined, with the usual interpretation, as V (A) divided by V (B). V ((A)) is the same as V (A).

4. If A is defined, then exp(A) is defined with meaning e^{A}.

5. If A is defined, and V (A) ≠ 0, then log(A) is defined, as the branch of the logarithm base e so that −π < ImaginaryP art(log(A)) ≤ π.

6. If A is defined and and V (A) ≠ 0, then A^{1/n} is defined and equal to exp(log(A)/n).

The operator V is called evaluation.

The complex numbers defined in this way are called closed form ([Chow]). We define the real closed form numbers to be the closed form numbers which happen to have zero imaginary part. Thus the real closed form numbers are closed under trigonometric functions as well as exponentiation and logarithms.

A field with good closure properties including the closed form numbers is the field of elementary numbers. These are numbers of the form q(α), where q is in Q Q Q[x_{1}, …, x_{n}], and α ∈ C C C^{n} is a non singular solution of a system of equations (p_{1}, …, p_{n}) = 0 and each p_{i} is in Z[x_{1}, …, x_{n}, e^{x_{1}}, …, e^{x_{n}}]. It has been shown that this is an effective field if the Schanuel conjecture is true. See [Richardson], [Richardson2].

The nested radical exponential and logarithmic expressions which do not use either the exponential or the logarithm will be called radical expressions. The numbers defined by radicals are the closed form numbers represented by such expressions.

The nested radical and exponential-logarithmic expressions can also be written as expression trees. Such trees have representations of integers at the leaves, and have interior nodes labelled with operator symbols. So, for example,

                       -
                    /    \
                   ^(1/3)
                           \
                 /
                -            ----      *  ----------------
             /     \                  /                    \
                                                             1/
         ^(1/5)    ^(1/5)          -                            \
            |         |         /    \                            ^(1/5)
                                                                     |
         32/25       27/5      +          *
                                                                    25
                           /    \       |       \
                                                 \
                         1    ^(1/5)    ^(1/5)    ^(1/5)
                                 |         |        |
                                 3         3        3

We will regard the expression trees and the expressions as equivalent from now on, since the translation from one form to the other is straightforward.

Please notice that although we have expressions here for n th roots, we do not have expressions for n th powers. If we want A^{2}, for example, we have to write it as A ∗ A.

2.2 Length of an expression

Our set of nested radical exponential and logarithmic expressions depends on a choice of canonical representation for the integers. Assume that we have chosen some base b for representation of the integers. We define the length of a non negative integer in this representation to be the number of digits base b which are used.

We define the length of a nested radical exponential and logarithmic expression by the following:

length(A + B) = length(A) + length(B) + 1 length(A − B) = length(A) + length(B) + 1 length(−A) = length(A) + 1 length(A ∗ B) = length(A) + length(B) + 1 length(A/B) = length(A) + length(B) + 1 length((A)) = length(A) + 2 length(A^{1/n}) = length(A) + length(n) + 1 length(e^{A}) = length(A) + 1 length(log(A)) = length(A) + 1. So, for example, in decimal notation, 4 − 3 ∗ (10)^{1/8} would have length 10,

since it has 5 digits and 3 operator symbols and two (unnecessary) brackets.

2.3 Expressions with variables

All of the above may be generalised by allowing a certain set x_{1}, …, x_{k} of variables to appear on the leaves of the expression trees, as well as representations of integers. Of course, in this case, the expressions represent partially defined complex valued functions of k complex variables. The same notion of length can be applied to such expressions, provided that we define the length of the variables in some way. We might take length(x_{i}) = i for each i.

2.4 Gap Functions

Definition 1 A gap function for the closed form numbers is a function g : Exp → R R R_{+}, where Exp is the set of nested radical exponential and logarithmic expressions, so that if x is a closed form number represented by an expression A, and x ≠ 0 then

|x| > 10^{−g(A)}

A gap function tells us the amount of decimal precision which is needed to distinguish a non zero number from zero. Of course gap functions exist. We hope that there is a computable gap function, and even an easily computable gap function.

We have a natural scale, i.e. length, on expressions; and we also have a natural scale, i.e. the logarithm of the absolute value, on the complex numbers which are non zero. The central question of this article is: How does the evaluation operator, V, behave with respect to these two scales?

2.5 Uniformity Conjecture

Using iterated exponentiation, it is possible to define very large numbers. Since we have division, it is also possible to define very small numbers with expressions involving iterated exponentiation, followed by division. There does not seem to be any other way to get very large numbers, or very small non zero numbers. ( Note that although we allow nth roots, we do not have nth powers. So we can not easily write a short expression for the result of a sequence of repeated squarings, for example.)

We consider an expression E to be a subexpression of itself.

We will say that an expression E is in expanded form if for any exponential subexpression e^{A} of E, we have |V (A)| ≤ 1.

It appears to be true that it is not possible to define any very large numbers, or any very small non zero numbers using small expressions in expanded form. The original motivation for this paper is an attempt to understand this somewhat vague idea.

Uniformity Conjecture: If E is an expression in expanded form, and V (E) ≠ 0, then |V (E)| is bigger than 1/N(k), where k is the length of E, and N(k) is the number of syntactically correct expanded form expressions of length ≤ k.

Expressions of length less than k can be coded as sequences of symbols of length k by padding with an initial sequence of right brackets. Therefore, if we have S symbols for operators and digits and brackets in our alphabet, the number of syntactically correct expressions of length ≤ k is bounded by S^{k}. In case we use decimal notation, for example, S would be 19 (counting the two brackets). In binary notation, S would be 11.

Roughly speaking, the conjecture says that the amount of base S precision which is needed to discriminate the value of an expanded form expression from zero is proportional to the length of the expression.

We will say that a number occurs at level k if it has an expanded form expression representing it with length no more than k.

A weaker form of the uniformity conjecture may be obtained by replacing N(k) by N(C ∗ k) for some universal constant C. A reason why at least this weaker form of the conjecture seems plausible is that if a number α occurs at level j, then the neighbourhood of 0 at level k may be translated to a subset of the neighbourhood of α at level k + j + 1, since if α is represented by A, and a number ϵ is represented by E, then α + ϵ is represented by A + E; and similarly a neighbourhood of α at one level translates to a subset of a neighbourhood of 0 at a higher level, and therefore we would expect all the neighbourhoods of closed form numbers, graded by level, to look alike, except for a change of scale.

The expressions I know which have small evaluations are not even close to being counterexamples. 4/3−10^{1/8} is zero to three decimal places; 7 log 2−3 log 5 is zero to 2 decimal places, for example. Even if we add π as a constant to our language, I still do not know a counterexample in the enlarged language. The famous 3 ∗ log(640320)/\sqrt{163} − π is only zero to 15 decimal places, whereas its syntactic length is 15 plus the length of π. We can replace π by log(−1)/(−1)^{1/2}, in which case the length of π would be 8.

It has been pointed out that the Uniformity conjecture is related to a family of conjectures, called Witness conjectures, originating with Joris van der Hoeven. See [van der Hoeven 95], [van der Hoeven 97], [van der Hoeven 2000]. For the family of constants we are considering, the witness conjectures may be stated as follows. For each positive rational number N, denote by Ξ_{N} the set of all nested radical exponential and logarithmic expressions A such that if E is any subexpression of A, then N^{−1} ≤ |V (E)| ≤ N. The Witness conjectures say that if A is in Ξ_{N}, then there is a function ω_{N}(n) so that |V (A)| ≤ e^{−ω_{N} (n)}, where n is the length of A. The strong witness conjecture is that we can take ω_{N}(n) = Kn, where K depends on N, and the weak witness conjecture is that we can take ω_{N}(n) = K^{n}, where K depends on N. Of course the Uniformity Conjecture is much more specific than either of the Witness Conjectures, since van der Hoeven does not attempt to estimate K. An especially interesting feature of the recent preprint is an attempt to extend the witness conjectures to a much wider class of constants. Although the Uniformity Conjecture and the Witness Conjectures were stated independently, it seems that the Uniformity Conjecture should be regarded as an extreme form of the Witness Conjecture. In the earlier paper by Van Der Hoeven referred to, I find the comment that some form of Witness Conjecture might imply the Schanuel Conjecture. I think this is possible, but do not see a proof. There is some discussion of this at the end of this paper.

Note that we can replace any expression which defines a value by an equivalent one in expanded form. But this is unlikely to be a good way to decide zero equivalence over the set of all nested radical exponential and logarithmic expressions. Joris van der Hoeven ([van der Hoeven 95]) suggests that expressions not in expanded form could be put into some sort of asymptotic form, as if the large numbers were exp-log functions which tended to infinity. I imagine that this is a good idea. For the rest of this article, however, we will just ignore expressions not in expanded form.

3 Mahler, Liouville, Baker, Waldschmidt estimates

3.1 Norm estimate

Theorem 1 Suppose α is an algebraic number with defining polynomial a_{d}x^{d} + ⋯ + a_{0} = a_{d}(x − α_{1}) … (x − α_{d}) in Z Z Z[x]. Then

log α ≥ −d Maximum(log |a_{d}| , log |α_{1}| , …, log |α_{d}|)

Proof.

|a_{d}α_{1} … α_{d}| = |a_{0}|, and a_{0} is a non zero integer, since the defining polynomial is chosen with minimal degree. So

|a_{d}α_{1} … α_{d}| ≥ 1

log |a_{d}| + log |α_{1}| + … log |α_{d}| ≥ 0

and the theorem follows from this.

□

3.2 Mahler Measure

Let p(x) be a polynomial in one variable with complex coefficients. Suppose

p(x) = a_{d}x^{d} + ⋯ + a_{0} = a_{d}(x − z_{1}) … (x − z_{d})

where z_{1} … z_{d} are the roots of p(x). Define the Mahler measure of p(x) by

M(p) = |a_{d}| ∏_{j=1}^{d} max(1, |z_{j}|)

We have, in general, M(x^{d}p(1/x)) = M(p) and M(p ∗ q) = M(p) ∗ M(q). Also, for any positive integer k, M(p(x^{k})) = M(p(x)).

In case α is an algebraic number, we define M(α) = M(p), where p(x) is a minimal defining polynomial for α in Z Z Z[x].

Lemma 1 If α and β are algebraic, with degrees d_{1} and d_{2} respectively, then

1. 1/M(α) ≤ |α| ≤ M(α)

2. M(α ∗ β) ≤ M(α)^{d_{2}}M(β)^{d_{1}}

3. M(α + β) ≤ 2^{d_{1}d_{2}}M(α)^{d_{2}}M(β)^{d_{1}}

4. If k is a positive integer, M(α^{1/k}) ≤ M(α)

5. If k is a positive integer, M(α^{k}) ≤ M(α)^{k}

6. M(1/α) = M(α)

Proof. All of this is standard, using the fact that the defining polynomials have integral coefficients. See [Mignotte], pp 148 ff.

Define the logarithmic Mahler measure to be the logarithm base 2 of the Mahler measure.

3.3 Liouville Estimate

Define the logarithmic height, h(p), of a polynomial p with integral coefficients to be the logarithm of the maximum of the absolute values of the coefficients. Define the logarithmic height of an algebraic number to be the logarithmic height of the minimal defining polynomial in Z Z Z[x]. We have:

Theorem 2 Liouville Estimate. Let ξ_{1}, …, ξ_{m} be algebraic numbers, of degrees d_{1}, …, d_{m} and logarithmic heights h_{1}, …, h_{m} respectively. Let d be the degree of the extension Q Q Q(ξ_{1}, …, ξ_{m}) over Q Q Q. Let P be a polynomial in Z Z Z[x_{1}, …, x_{m}], of degree N_{i} in x_{i}. If P (ξ_{1}, …, ξ_{m}) ≠ 0, then

−d(h(P) + ∑_{i=1}^{m}(N_{i}h_{i}/d_{i}) + 2N_{i}) ≤ log |P (ξ_{1}, …, ξ_{m})|

For proof, see [Lang].

3.4 Examples

Consider a linear form in radicals.

λ = b_{1}(a_{1})^{1/n_{1}} + b_{2}(a_{2})^{1/n_{2}} + ⋯ + b_{k}(a_{k})^{1/n_{k}} + b_{k+1}, with b_{i} ∈ Z Z Z, and n_{i}, a_{i} positive natural numbers for all i. Assume λ ≠ 0. Then we get the following contrasting estimates. (Note that logarithms here are base 2.)

1. Norm estimate and Mahler measure. We have deg(λ) ≤ ∏ n_{i}, and the denominator of λ is 1. So we get

log |λ| ≥ −(∏ n_{i})(log(|b_{k+1}| + ∑_{i≤k} |b_{i}| |a_{i}|^{1/n_{i}}))

2. Liouville Estimate.

log |λ| ≥ −(∏ n_{i})(log Max_{i}(|b_{i}|) + ∑_{i} log(|a_{i}|)/n_{i} + 2k)

3. Uniformity Conjecture.

log |λ| ≥ −C(∑ log |n_{i}| + ∑ log |a_{i}| + ∑ log |b_{i}| + 3k)

, where C ≤ log(19).

The most striking feature of the above is that in all the earlier estimates the precision needed increases as the product of the radical degrees; but according to the uniformity conjecture all that is needed is the sum of the logarithms. Thus even in this simple algebraic case, the uniformity conjecture would imply quite strong new results.

3.5 Baker-Waldschmidt

See [De Weger].

Theorem 3 (Baker-Waldschmidt) Suppose p_{1}, …, p_{n} ∈ Z Z Z with 2 ≤ p_{1} < ⋯ < p_{n} and that (Q Q Q(p_{1}^{1/2}, …, p_{n}^{1/2}) : Q Q Q) = 2^{n}. Let b_{1} …, b_{n} ∈ Z Z Z, with B = Max_{1≤i≤n} |b_{i}|. Suppose λ = b_{1} log p_{1} + ⋯ + b_{n} log p_{n} ≠ 0. Let V_{i} = Max(1, log p_{i}), for i = 1, …, n. Let ω = V_{1} … V_{n}. Let

C_{1} = 2^{9n+26}n^{n+4}ω log(eV_{n−1})

C_{2} = C_{1} log(eV_{n})

Then

|λ| > e^{−(C_{1} log B+C_{2})}

.

This should be compared with the uniformity conjecture, which predicts:

|λ| > 19^{−(∑ length(p_{i})+length(b_{i})+2n−1)}

In this case, the most striking difference is that the coefficient C_{1} in the Baker-Waldschmidt result increases as the product of the lengths of the p_{i}, whereas in the prediction from the uniformity conjecture, only the sum of the lengths appears.

Patrice Philippon relates a similar lower bound on linear forms in logarithms with the abc conjecture. See [PP], [PP2].

3.6 Thue-Siegel-Roth

See [HS], [Sprindzhuk].

Theorem 4 (Thue-Siegel-Roth) For any algebraic number α and for any δ > 0

|p/q − α| > q^{−(2+δ)}

for all but finitely many (p/q) in Q Q Q.

The uniformity conjecture would predict that if A is an expression representing α then:

|p/q − α| > 1/N(k), where k is the length of p/q − A, ie k = length(p) + length(q) + length(A) + 2)

provided α ≠ p/q. In this case the inequality directly implied by the uniformity conjecture is weaker than that of Thue-Siegel-Roth, but does not allow exceptions. So even in this case, the uniformity conjecture would imply new results. On the other hand, the Thue-Siegel-Roth theorem implies a bound on the number of counterexamples to the uniformity conjecture of the form α − p/q, for fixed algebraic closed form α.

Suppose we represent integers base 10, and therefore count length base 10.

Proposition 1 Suppose α is an algebraic closed form number represented by an expression A. Then there are at most only finitely many p/q in Q Q Q so that

|α − p/q| < 1/N(k) with k = length(p) + length(q) + 2 + length(A).

Proof. Suppose, for the sake of a contradiction, that α is a fixed algebraic closed form number and that there are infinitely many counterexamples to the uniformity conjecture of the form

α − p/q

Let (p_{i}/q_{i}) be a sequence of rationals, with q_{i} → ∞, and k_{i} = length(p_{i}) + length(q_{i}) + length(α) + 2 and

|α − p_{i}/q_{i}| < 1/N(k_{i})

.

We have N(k) ≥ 10^{k(1+ϵ)} for some ϵ > 0.

Also p_{i}/q_{i} → α and α ≠ 0, and length(q_{i}) → ∞, so length(p_{i})/length(q_{i}) → 1.

Thus

|α − p_{i}/q_{i}| < 10^{−(1+ϵ/2)2(length(q_{i})+1)} for sufficiently large i.

Thus for some ϵ > 0 and for infinitely many p/q in Q Q Q

|α − p/q| < q^{−(2+ϵ)}, contradicting Thue-Siegel-Roth.

Thus although there may be counterexamples to the uniformity conjecture of the form a^{1/n} − p/q, we should not expect very many of them.

4 Computational Consequences

4.1 Lazy exact computation

We hope eventually to extend the possibility of exact computation beyond the field of rational numbers in such a way that each expression for a real number can easily be approximated to any desired precision. One important step in this direction would be to understand how to compute with the nested radical and exponential-logarithmic expressions.

Even without the exponential and the logarithm, basic questions about nested radical expressions may seem quite difficult to decide. In particular, equality is not well understood, as illustrated by the following examples, from [Davenport, p93].

\sqrt{5 + 2\sqrt{6}} + \sqrt{5 − 2\sqrt{6}} = 2\sqrt{3}
\sqrt{16 − 2\sqrt{29} + 2\sqrt{55 − 10\sqrt{29}}} = \sqrt{22 + 2\sqrt{5}}
− \sqrt{11 + 2\sqrt{29}} + \sqrt{5}
\sqrt[3]{\sqrt[5]{32/5} − \sqrt[5]{27/5}} = (1 + \sqrt[5]{3} − \sqrt[5]{3}^{2})/\sqrt[5]{25}
\sqrt{112 + 70\sqrt{2} + (46 + 34\sqrt{2})\sqrt{5}} = 5 + 4\sqrt{2} + (3 + \sqrt{2})\sqrt{5}

Open Problem 1 What is the computational difficulty of deciding V (A) = 0, where A is a radical expression, i.e. a radical exponential logarithmic expression with no exponential or logarithmic terms?

See [Strsebonski], [Pohst2], [Loos], [Johnson], [Hur], [Langley] for some methods currently used or proposed to solve such problems.

In particular, it would be interesting to know whether or not the zero equivalence problem for radical expressions can be solved in a number of steps which is bounded by some polynomial in the length of the expression. In other words, is this basic problem tractable in the sense of Blum-Smale-Shub? See [BSS].

We would also like to know:

Open Problem 2 What is the computational complexity of finding V (A) to n decimal places, given nested radical exponential and logarithmic expression A ?

See proposition 3 of this article for a very crude upper bound.

Note that for this question we want the complexity in terms of the two input parameters, length(A) and n. We know that for fixed A, we can approximate to n decimal places in a number of steps bounded by O(log(n)m(n)), where m(n) is the complexity of multiplication of n digit numbers. See [Borwein].

In any case, it is clear that the Uniformity conjecture implies easy decidability of the zero equivalence problem for closed nested radical exponential and logarithmic expressions.

4.2 Inverse symbolic calculation

The uniformity conjecture implies that the decimal approximation of precision log_{10}(19) ∗ 2n is a code for the closed form expression, with integers in decimal notation, and length n, with that value. This implies the existence of a potentially quite useful inverse symbolic calculator, that is a method of deriving a closed form expression from a decimal approximation.

4.3 Unwound Straight Line Programs

Consider expression trees with integers or variables on the leaves and internal nodes labelled with operators for addition, subtraction and multiplication. We will call these unwound straight line programs. This is a compact way to represent multivariate polynomials. One of the difficult problems in this area is how efficiently to recognise the zero polynomial. (See [Zippel] for a discussion of this problem.) This could be done by substitution of algebraically independent values. For example, if p_{1}, …, p_{n} are the first n prime numbers, we know that e^{1/\sqrt{(}p_{1})}, …, e^{1/\sqrt{(}p_{n})} are algebraically independent. If we accept the Schanuel conjecture, we know that log(p_{1}), …, log(p_{n}) are algebraically independent. Thus, assuming the Schanuel conjecture, if the variables are (x_{1}, …, x_{n}), we could substitute (log(p_{1}), …, log(p_{n})), where (p_{1}, …, p_{n}) are the first n primes. If k is the length of the resulting nested exponential and logarithmic expression, we could recognise whether or not the original polynomial was zero by approximation with decimal precision log_{10}(19)k.

Suppose expression tree T represents polynomial P_{T} in Z Z Z[x_{1}, …, x_{n}]. Define h(T) to be the maximum length of the integers on the frontier of T. Define s(T) to be the number of nodes in T. Define A_{T} to be the nested radical and exponential-logarithmic expression obtained by substituting log(p_{i}) for x_{i}, for i = 1 … n, where p_{i} is the i th prime. Note that A_{T} is in expanded form. The length of p_{i} is no more than i. Thus the length of A_{T} is bounded by

s(T) + s(T)h(T) + s(T)n

So far we have:

Proposition 2 (Assuming the Uniformity Conjecture and the Schanuel conjecture.) P_{T} is the zero polynomial if and only if |V (A_{T})| < 1/N(k) where k = s(T) + s(T)h(T) + s(T)n.

Also,

Proposition 3 (Assuming the Uniformity Conjecture and the Schanuel Conjecture.) The computational bit complexity of deciding whether or not P_{T} is the zero polynomial is bounded by

O(s(T) log(k)m(s(T)k))

where k = s(T) + s(T)h(T) + s(T)n

and m(k) is the complexity of multiplication of two k digit numbers.

Proof. We need O(k) decimal places for the output of A_{T} so that we can apply the previous proposition.

The value output by a tree A_{T}, or by any of its subtrees is bounded in absolute value by 10^{O(k)}. This means that at most O(k) decimal places of precision can be lost at each computation step. So at most s(T)O(k) decimal places of precision are lost in the whole computation.

Thus we need to do the whole computation with O(s(T)k) decimal places. We can get j decimal places for each log p_{i} in O(m(j) log j) steps, where m(j)

is the complexity of multiplication of j digit numbers. So we can get the necessary O(s(T)k) decimal places for these n logarithms in O(s(T) log(k)m(s(T)k)) steps, since n < s(T) < k. Addition, subtraction and multiplication to j decimal places can be done in O(m(j)) steps. So the rest of the computation can be done in O(s(T) log(k)m(s(T)k) steps. Thus the whole computation can be done in a number of steps bounded by O(s(T) log(k)m(s(T)k)).

Of course this could be done without the Schanuel conjecture, using another substitution.

5 Search for a Counterexample to the Uniformity Conjecture

5.1 Good rational approximations

If α is real we can look for good rational approximations to α by searching for large coefficients in the continued fraction expansion of α. In this way we might find counterexamples or near counterexamples to the Uniformity conjecture of the form α − p/q.

5.2 Near Integer Relations

If a is a vector of n real numbers, an integer relation for a is a non zero integer vector c so that c^{T} a = 0. A near integer relation is a non zero integer vector c so that c^{T} a has “small” absolute value.

We can make the notion of “small” precise if a consists of closed form numbers. Define length(a) to be the sum of the lengths of the components, considering these as closed form numbers. We will say that c^{T} a is small if

|c^{T} a| < 10^{−(length(c)+length(a)+2n−1)}

These near integer relations include all possible counterexamples to the uniformity conjecture of the form c^{T} a.

For fixed a, we can search for such near integer relations using the LLL algorithm.

Let the Euclidean length of a vector v ∈ R R R^{n} be, as usual (∑ v_{i}^{2})^{1/2}.

Suppose B = {v^{(1)}, …, v^{(n)}} is a set of n vectors in R R R^{n} which are linearly independent over R R R. By the lattice spanned by B we mean the set

L = ∑ r_{i}v^{(i)} : r_{i} ∈ Z Z Z

This lattice has dimension n and rank n. The determinant of the lattice, det(L) is the determinant of any matrix of real numbers whose rows span the lattice. This is independent of basis.

A lattice reduction algorithm, such as LLL, finds a reduced basis for a given lattice, the first vector of which has Euclidean length at most 2^{(n−1)/2}m(L), where m(L) is the Euclidean length of the shortest non zero vector in the lattice. The first vector in a reduced basis also has Euclidean length bounded by 2^{(n−1)/4}det(L)^{1/n}. For definition of reduced basis and proofs of basic properties, see [HJLS], [HST].

This can be used to find near integer relations in the following way. Suppose we are given a = (a_{1}, …, a_{n}), and let (a′_{1}, …, a′_{n}) be a vector of their rational approximations. Let M be a large rational constant. Let A be the n by n matrix which is obtained from the n by n identity matrix by replacing the last column by the transpose of (Ma′_{1}, …, Ma′_{n}). Consider the lattice L spanned by the n dimensional vectors v^{(i)}, 1 ≤ i ≤ n, which are the rows of the matrix A.

If V is a short vector in a reduced basis for L

V = (w_{1}, …, w_{n−1}, M ∑_{i≤n} w_{i}a′_{i})

then

|∑ w_{i}a′_{i}|

is small and thus (w_{1}, …, w_{n}) is a good candidate for a near integer relation for (a_{1}, …, a_{n}).

The problem now is to pick the precision of the approximation and the size of the multiplier M in such a way the first vector in a reduced basis can be used to indicate the non existence of small c^{T} a with some conditions on c. We will fix length(c) and also put an upper bound on the length of each component of c.

Assume that (a_{1}, …, a_{n}) is ordered so that |a_{n}| is maximal among |a_{i}|. The determinant of the lattice is Ma_{n}.

Suppose we are looking for small c^{T} a with Max(length(c_{i}) = m, and thus length(c) ≤ nm. Let

M = 10^{length(c)+m+length(a)+2n−1}

.

Approximate a with precision more than (n + 1)m + length(a) + 2n − 1. Find the reduced basis. If b_{1} is the first vector in the reduced basis, we expect

|b_{1}| ≤ 2^{(n−1)/4}(Ma_{n})^{1/n}

However a small c^{T} a with length(c_{i}) ≤ m for all i would imply

c^{T} a < 10^{−(length(c)+length(a)+2n−1)}, and thus each component of the shortest vector in the lattice would have length no more than m, and thus

|b_{1}| ≤ 2^{(n−1)/2}n^{1/2}10^{m}

Therefore, if this condition does not happen, we can eliminate the possibility of small c^{T} a of this kind. This can be used to eliminate some parts of the search space for counterexamples.

5.3 Various Results

Assorted near counterexamples 12^{(1/17)}−4015/3496. This is 0 to 10 decimal places. Quite small, but not small enough. I found this by looking for large numbers in the continued fraction expansions of n th roots.

17^{(1/25)} − 28/25 is zero to 6 decimal places. Also found with continued fractions.

3 ∗ log(640320)/\sqrt{163} − π. This is famous for being small, but it is only 0 to 15 decimal places.

π − 355/113, zero to 6 decimal places, could be found by looking for large numbers in the continued fraction expansion of π, and is also well known.

199 log(3) + 142 log(7) − 183 is zero to 8 decimal places. This was found with LLL.

In [De Weger] LLL is used to find small linear forms in logarithms, and many results are tabulated. No counterexample to the uniformity conjecture is found.

Some examples found by students Students in my computer algebra course examined a^{1/n}−p_{k}/q_{k} ≠ 0 for natural numbers a between 2 and 100, and natural numbers n between 2 and 100, with p_{k}/q_{k} the kth convergent of the continued fraction approximation for values of k up to 80, and found no counterexamples to the uniformity conjecture. Some small numbers they found were:

2^{1/8} − 494/453, which is 0 to 6 decimal places ; 3^{1/14} − 53/49, which is 0 to 6 decimal places ; 3^{1/6} −6/5, which is 0 to 4 decimal places ; 7^{1/8} −311830/244501, which is 0 to 14 decimal places ; 11^{1/5} − 21/13, which is 0 to 5 decimal places ; 11^{1/6} − 6772/4541, which is 0 to 10 decimal places ; 14^{1/95} − 73/71, which is 0 to 7 decimal places ; 21^{1/20} − 7243/6958, which is 0 to 11 decimal places ; 27^{1/8} − 77/51, which is 0 to 6 decimal places ; 31^{1/97} − 115/111, which is 0 to 8 decimal places ; 38^{1/50} − 92/83, which is 0 to 8 decimal places ; 61^{1/11} − 93/64, which is 0 to 6 decimal places ; 65^{1/11} − 19/13, which is 0 to 6 decimal places ; 89^{1/6} − 374/177, which is 0 to 9 decimal places ; 109^{1/5} − 23/9, which is 0 to 6 decimal places ; 544^{1/6} −20/7, which is 0 to 6 decimal places ; 823^{1/6} −1849/604, which is 0 to 13 decimal places.

The following were found with LLL:

143 log(3) − 183 log(7) + 199 is zero to 8 decimal places.

4 log(3) + 13^{1/2} − 8 is zero to 6 decimal places.

Thanks to John Hillier, Simon Attfield, Mark Wilcox, Mark Waddingham, Steven Olney, Jonathan Brown, Jake Holdridge and Emma Jones for these examples.

Linear forms in radicals: an example Consider the linear form

λ = c_{1}\sqrt{2} + c_{2}\sqrt{3} + c_{3}

Suppose there were a counterexample to the uniformity conjecture with the length(λ) = k + 8, where k is the sum of the lengths of c_{i}, which are assumed to be integral. Let m be the maximum length of the coefficients c_{i}. In the counterexample, λ must be small, and so

2m ≤ k ≤ 3m

Let j = k + 8 + m, and take LLL multiplier M = 10^{j}, as described in the previous section. Then if b_{1} is the first vector in a reduced basis, we must have

|b_{1}| ≤ 2\sqrt{(}3)10^{m}

.

An upper bound for m is (j − 8)/3. The LLL algorithm was run for j = 1, ...50. The results all violate this constraint, and thus show that there is no counterexample of this form with coefficients using up to 12 digits. This is quite an easy computation, and it is clear that other regions of the search space could be investigated in this way.

5.4 A confession

The search for counterexamples has so far concentrated on linear forms in a few simple terms. This is because we have reasonably good tools for such a search. I have been trying to eliminate the possibility that the unfound items are under the street lamp since I don’t know how to search anywhere else.

6 Extension to the elementary numbers

An elementary number is a number of the form q(α) where q ∈ Z Z Z[x_{1}, …, x_{n}], and α is a point in C C C^{n} which is a non singular solution of a system of equations S(x) = 0, and S = (p_{1}, …, p_{n}) with each p_{i} a polynomial with integral coefficients in x_{1}, e^{x_{1}}, …, x_{n}, e^{x_{n}}.

Such a number will be defined by:

η = q(α), S(α) = 0, α ∈ B

where B is a ball in C C C^{n} which contains the point α and which does not contain any other solution of S(x) = 0. (The assumption that α is a non singular solution means that the Jacobian of S, evaluated at α is non zero.)

We will say that such a definition is in expanded form if B is the unit ball around the origin in C C C^{n}.

Define the length of a power product x_{1}^{j_{1}} … x_{n}^{j_{n}}e^{k_{1}x_{1}} … e^{k_{n}x_{n}} to be the sum of the lengths of the degrees, length(j_{1}) + ⋯ + length(j_{n}) + length(k_{1}) + ⋯ + length(k_{n}). Define the length of a monomial to be the length of the coefficient plus the length of the power product. Define the length of a sum of k monomials to be the sum of the lengths of the monomials. This gives a definition of length for all polynomials in Z Z Z[x_{1}, e^{x_{1}}, …, x_{n}, e^{x_{n}}]

Suppose elementary number η is defined, in expanded form, by:

η = q(α), S(α) = 0, B

where B is the unit ball around the origin. Define the size of this definition to be the product of the sum of the lengths of the polynomials including q and the product of the total degrees of the polynomials in S.

(length(p_{1}) + ⋯ + length(p_{n}) + length(q))(degree(p_{1}) ∗ ⋯ ∗ degree(p_{n}))

where S = (p_{1} …, p_{n}).

Uniformity conjecture for elementary numbers If η is a non zero elementary number and has an expanded form definition of size n, then |η| > 10^{−n}.

7 Relation to the Schanuel Conjecture

The Schanuel Conjecture If α_{1}, …, α_{m} are complex numbers which are linearly independent over Q Q Q, then (α_{1}, …, α_{m}, e^{α_{1}}, …, e^{α_{m}}) has transcendence rank at least m.

It has been shown that if the Schanuel conjecture is true, then the zero equivalence problem for closed form numbers is decidable. Thus the Schanuel conjecture implies the existence of a computable gap function. See [Richardson], [Richardson2].

It seems that it might be possible to prove part of the Schanuel conjecture, via Gelfond’s method, from the uniformity conjecture. For a good exposition of Gelfond’s method, see [Lang]. Roughly speaking, Gelfond’s method would construct a function F (t) with a large number of roots from the existence of a counterexample to the Schanuel conjecture. A closed form number F (w) would then be found which has a fairly small length but is non zero. The maximum modulus principle (an analytic function defined on an open set including a ball has modulus inside the ball bounded by maximum modulus on the boundary of the ball) is then applied to show that the modulus of F (w) is so small that it contradicts the uniformity conjecture.

It would be nice to show the following.

Conjecture If K is a field of closed form numbers with transcendence rank d, and the uniformity conjecture is true for numbers in K, and α_{1} …, α_{m} are in K, and are linearly independent over Q Q Q, and m > d then e^{α_{1}}, …, e^{α_{m}} are not all in K.

I am not able to prove this or anything like it. Here is a small result which shows how the Gelfond method can be used.

We will say that (x_{1}, …, x_{d}, y) is a proper set of generators of a subfield F of C C C if x_{1}, …, x_{d} are algebraically independent and y is algebraic and integral over Z Z Z[x_{1}, …, x_{d}], and F is Z Z Z(x_{1}, …, x_{d})[y]. Any number in such a field has a canonical form as a polynomial in Z Z Z(x_{1}, …, x_{d})[y] with y-degree less than the degree of y over Z Z Z[x_{1}, …, x_{d}]. If A_{1}, …, A_{j} are numbers in K and we wish to solve an equation

a_{1}A_{1} + ⋯ + a_{j}A_{j} = 0

for integers a_{1}, …, a_{j}, we can do this by putting A_{1}, …, A_{j} into canonical form in K and replacing this equation by a system of equations, one for each power product which appears in the canonical forms. The number of such equations is bounded in terms of the degree in (x_{1}, …, x_{d}) of A_{1}, …, A_{j}.

If E is an expression in canonical form for an element of field F, with proper set of generators (x_{1}, …, x_{d}, y), let h(E) be the maximum of the lengths of the integral coefficients in E; and let deg(E) be the maximum of the degrees of any x_{i} in E. The number of integral coefficients in E is then bounded by O(deg(E)^{d}). Using this, we can bound h(E_{1} ∗ E_{2}) in terms of h(E_{1}) and h(E_{2}) and deg(E_{1}) and deg(E_{2}).

Lemma 2 Suppose E_{1}, E_{2}, and E_{3} are canonical form elements of field F, with proper set of generators. Then

1. If E_{3} = E_{1} ∗ E_{2} then deg(E_{3}) ≤ O(deg(E_{1}) + deg(E_{2})) and h(E_{3}) ≤ O(h(E_{1}) + h(E_{2}) + deg(E_{1}) + deg(E_{2}))

2. If E_{2} = E_{1}^{j}, then deg(E_{2}) ≤ O(j(h(E_{1})+deg(E_{1}))) and h(E_{2}) ≤ O(j(h(E_{1})+ deg(E_{1})))

The constant multipliers implied in the big O notation do depend on the defining polynomial for y over Z Z Z[x_{1}, …, x_{d}], but can be chosen independent of E_{1}, E_{2}, E_{3}, j. For a proof of this standard result, see [Lang], Ch V, Lemma 1.

Proposition 4 (Assuming Uniformity Conjecture.) Let K be a field of closed form numbers with transcendence rank d, and proper set of generators (x_{1}, …, x_{d}, y). Suppose c_{1}, …, c_{d_{1}} are complex numbers which are linearly independent over Q Q Q, and α_{1}, … α_{d_{2}} are complex numbers which are linearly independent over Q Q Q. Then not all of

e^{c_{i}α_{j}}, for 1 ≤ i ≤ d_{1}, 1 ≤ j ≤ d_{2}

can be in K, provided (d_{1} + d_{2})(d + 1) ≤ d_{1}d_{2}

Proof. For the sake of a contradiction, suppose that (d_{1} + d_{2})(d + 1) ≤ d_{1}d_{2} and also e^{c_{i}α_{j}} in K for all i, j. In all the following, d, d_{1}, d_{2} are fixed. Let n be a large whole number. We will eventually let it go to infinity. Define S_{n} to be the set of numbers of the form ∑_{1≤i≤d_{1}} n_{i}c_{i} where each n_{i}

is a natural number with |n_{i}| ≤ n. Since the c_{i} are linearly independent, the number of distinct numbers in S_{n} is (n + 1)^{d_{1}}.

For j = 1, …, d_{2}, define f_{j}(t) = e^{α_{j}t}. These functions are multiplicatively independent. Each f_{j} maps S_{n} into K. Form

F (t) = ∑ a_{(i)}x_{1}^{i_{d_{2}+1}} … x_{d}^{i_{d_{2}+d}}f_{1}^{i_{1}} … f_{d_{2}}^{i_{d_{2}}}

where (i) = (i_{1}, … i_{d_{2}+d}), and 1 ≤ i_{1}, …, i_{d_{2}} ≤ r and 1 ≤ i_{d_{2}+1}, …, i_{d_{2}+d} ≤ rn, and r = cn^{d_{1}/d_{2}}, for some fixed number c.

We now have d, d_{1}, d_{2} fixed, n going to infinity, and r defined in terms of n, depending on fixed c, which will be chosen later, but will be independent of r and n.

We need to solve for integer coefficients a_{(i)}, not all zero, so that F (z) = 0 for all z in S_{n}.

The number of unknowns is the number of a_{(i)}, that is r^{d_{2}}(rn)^{d}.

For each z in S_{n}, we put F (z) in canonical form, with respect to the proper set of generators (x_{1}, …, x_{d}, y). We need a bound on the degrees in (x_{1}, …, x_{n}) which can occur in this canonical form. For z in S_{n}, f_{j}(z)^{i_{j}} is a product of O(rn) numbers from a fixed finite set, {e^{c_{i}α_{j}} : i ≤ d_{1}, j ≤ d_{2}}, of numbers in K. Therefore, according to the Lemma preceeding, the degrees in (x_{1}, …, x_{d}) of F (z), for z in S_{n} are bounded by O(rn). When we put each equation F (z) = 0 into canonical form, we get a system of equations, one for each distinct power product in the canonical form. The number of equations which must be solved is thus bounded by O(n^{d_{1}}(rn)^{d}). The integral coefficients in these equations have length bounded by O(rn), according to the Lemma preceeding. Now pick the fixed number c so that the number of unknowns is more than twice the number of equations, and thus so that there is a solution in integers a_{(i)} with length bounded by O(rn).

We know that F (t) is not identically zero. Let s be the first number bigger than n so that for some w in S_{s+1} we have F (w) ≠ 0. There must be such an s since otherwise F (t) has too many roots, in fact a dense set of roots. (We expect s = n.) Consider F (w). We can show that if n is picked sufficiently large, F (w) will be a counterexample to the uniformity conjecture.

Put F (w) in canonical form in Z Z Z(x_{1}, …, x_{d})[y]. The length of F (w) is bounded by O((rs)^{d+1}).

Define

G(w, t) = F (t) ∏_{z∈S_{s}}(w − z)/ ∏_{z∈S_{s}}(t − z)

F (z) = 0 for all z in S_{s}.

G(w, t) is analytic, and F (w) = G(w, w). By the maximum modulus principle, the modulus of F (w) is bounded by the modulus of G(w, t) for t on a circle which includes w in its interior.

Consider a circle of radius R = s^{1+ϵ} for some small positive ϵ. For s sufficiently large, this circle includes all of S_{s+1}.

Assume |t| = R. Then

|(w − z)/(t − z)| < s^{−ϵ} for z in S_{s} and thus the product of all these numbers is bounded by s^{−ϵ(s+1)^{d_{1}}} for sufficiently large s. It follows that

log | ∏_{z∈S_{s}}(w − z)/ ∏_{z∈S_{s}}(t − z)| < −K_{1}(s^{d_{1}} log s)

for some constant K_{1} > 0. Also,

log |F (t)| ≤ O(s^{1+ϵ}r) ≤ O(s^{1+ϵ+d_{1}/d_{2}})

since r = cn^{d_{1}/d_{2}}. This is dominated by K_{1}s^{d_{1}} log s.

We get that log |F (w)| is bounded above by −K_{2}(s^{d_{1}} log s) for some constant K_{2} > 0.

On the other hand, the number of monomials in the canonical form of F (w) is bounded by O(rs)^{d}, and the integral coefficients have length bounded by O(rs), and thus the length of F (w) (in canonical form) is bounded by O((rs)^{d+1}), and this is bounded by O(s^{(d_{1}+d_{2})(d+1)/d_{2}}).

This either contradicts the uniformity conjecture, or our assumption that (d_{1} + d_{2})(d + 1) ≤ d_{1}d_{2}.

□

Here is a sample consequence.

Corollary 1 (Assuming the Uniformity Conjecture.) All the numbers e^{e^{n}} can not be in Q Q Q(e) for n = 0, 1, …, 6.

Proof. Take d = 1 and d_{1} = 4, d_{2} = 4 in the proposition, and c_{i} = e^{i−1} = α_{i}.

References

[Baker] A. Baker, Transcendental number theory, CUP, 1975

[Borwein] J. M Borwein and P. B. Borwein, On the Complexity of Familiar Functions and Numbers, SIAM Review, Vol 30, No 4, Dec 1988, pp 589-601

[BSS] Blum, Cucker, Shub, Smale, Real Complexity and Computation, Springer [Chow] T. Y. Chow, What is a Closed-Form Number?, American Mathe-

matical Monthly, Vol 106, No 5, 1999, pp 440-448

[Davenport] J. Davenport, Y. Siret and E. Tournier, Computer Algebra, Aca-

demic Press, 1993.

[De Weger] B. M. M. De Weger, Solving exponential Diophantine equations using lattice basis reduction algorithms, J. Number Theory 26 (1987) 325-367.

[HJLS] J. Håstad, B. Just, J.C. Lagarias, C.P.Schnorr, Polynomial time algorithms for finding integer relations among real numbers, SIAM J. Comput. 18 (1989). pp 859-881.

[HS] M. Hindry and J. Silverman, Diophantine Geometry, An Introduction, Springer Graduate Texts in Mathematics, 2000

[HST] E. Hlawka, J. Schoissengeier, R. Taschner, Geometric and Analytic Number Theory. Springer Verlag, 1991

[Hur] Namhyun Hur, and James H. Davenport, An exact Real Arithmetic with Equality Determination, draft, (Bath U)

[Johnson] J. R. Johnson, Real Algebraic Number Computation using Interval Arithmetic, ISSAC ’92, pp 195-205

[Koiran] P. Koiran, A weak version of the Blum, Shub and Smale Model, FOCS ’93, pp 486-495; also in JCSS 54 (1), pp 177-189, 1997

[Langley] S. Langley, and D. Richardson, Bounds on Algebraic Expressions, preprint

[Lang] S. Lang, Introduction to Transcendental Numbers, Addison Wesley, 1966

[Loos] R. Loos, Computing in Algebraic Extensions , Computing, 4, (Suppl) pp 173-187, 1982

[Sombra] Martin Sombra, Estimaciones para el Teorema de Ceros de Hilbert, Tesis, Departamento de Matematica, Facultad de Ciencias Exactas y Naturales, 1998.

[Philippon] P. Philippon, Sur des hauteurs alternatives, I, Math Ann. 289 (1991), pp 255-283; II Ann. Inst. Fourier 44 (1994), pp 1043-1065; III, J. Math. Pures Appl. 74 (1995), pp 345-365

[PP] P. Philippon, Quelques remarques sur des questions d’approximation diophantine, Bull Austral. Math. Soc., Vol 59(2), (1999), pp 323-334.

[PP2] P. Philippon, Addendum a quelques remarques sur des questions d’approximation diophantine, Bull Austral. Math. Soc., vol 61(1), (2000), pp 167-169.

[Pohst1] M. Pohst, Algorithmic Algebraic Number Theory

[Pohst2] M. Pohst, On Validated Computing in Algebraic Number Fields, J. Symbolic Computation 24, pp 657-666, 1997

[Macintyre] A. Macintyre, A. Wilkie, On the decidability of the real exponential field, in Kreiseliana, About and Around Georg Kreisel, A.K. Peters, 1996, pp 441-467.

[Mignotte] M. Mignotte, Mathematics for Computer Algebra, Springer Verlag, 1991

[Richardson] D. Richardson, How to Recognise Zero, J. Symbolic Computation

(1997), 24, pp 627-645

[Richardson2] D. Richardson, Multiplicative Independence of Algebraic Numbers and Expressions, Mega2000 conference Bath June 2000, to appear in Journal of Pure and Applied Algebra.

[Sprindzhuk] V. G. Sprinkzhuk, Achievements and Problems in Diophantine Approximation Theory, Russian Mathematical Surveys 35 (4), 1980, pp 1-80

[Strsebonski] A. W. Strsebonski, Computing in the Field of Complex Algebraic

Numbers, J. Symbolic Computation 24, pp 647-656, 1997

[van der Hoeven 95] Joris van der Hoeven, Automatic Numerical Expansions, in J.C. Bajard, D. Michelucci, J.M. Moreau, and J.M. Muller, editors, Proc. of the conference “Real numbers and computers”, Saint-Etienne, France, Pages 261-274, 1995

[van der Hoeven 97] Joris van der Hoeven, Automatic Asymptotics, Ph.D. thesis, Ecole

Polytechnique, 1997.

[van der Hoeven 2000] Joris van der Hoeven, Zero-testing, witness conjectures and dif-

ferential diophantine approximation, Preprint

[Zippel] R. Zippel, Effective Polynomial Computation, Kluwer Academic Publishers, 1993